#leetcode题目87：扰乱字符串
#难度：困难

class Solution:
    def isScramble(self, s1, s2):
        len1, len2 = len(s1), len(s2)
        if len1 != len2:
            return False
        dp = [[[False] * (len1 + 1) for j in range(len1)] for i in range(len1)]
        for i in range(len1):
            for j in range(len1):
                dp[i][j][1] = s1[i] == s2[j]
        for k in range(2, len1 + 1):
            for i in range(len1 - k + 1):
                for j in range(len1 - k + 1):
                    for w in range(1, k):
                        # 0-w,w-k
                        # s1 s11 s12
                        # s2 s21 s22
                        if dp[i][j][w] and dp[i + w][j + w][k - w]:
                            dp[i][j][k] = True
                            break
                        if dp[i][j + k - w][w] and dp[i + w][j][k - w]:
                            dp[i][j][k] = True
                            break
        return dp[0][0][len1]


#测试数据
s1 = "great"
s2 = "rgeat"
#预期输出：True
solution = Solution()
print(solution.isScramble(s1, s2))

s1 = "abcde"
s2 = "caebd"
#预期输出：False
solution = Solution()
print(solution.isScramble(s1, s2))
